/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/permutation-index-ii
   @Language: C++
   @Datetime: 19-03-28 13:56
   */

class Solution {
public:
	/**
	 * @param A: An array of integers
	 * @return: A long integer
	 */
	long long permutationIndexII(vector<int> &A) {
		// write your code here
		long long sum=0, fact=1, n=1;
		map<int,int> rights;	// num, count
		for(int i=A.size(); i--;){
			rights[A[i]]++;
			for(const auto &p:rights){
				if (p.first==A[i]) break;
				sum += fact*p.second/rights[A[i]];
			}
			fact = fact*(n++)/rights[A[i]];
		}
		return sum+1;
	}
};
